package com.atguigu.distributed.lock.leecode;

public class KthLarge {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9,10};
        KthLarge kthLarge = new KthLarge();
        System.out.println(kthLarge.findKth(arr,2));
    }
    public int findKth(int[] arr,int k){
        return quickSort(arr, 0, arr.length-1, k);
    }
    public int partion(int[] a,int low,int high){
        int temp=a[low];
        while (low<high){
            //小于标杆的在右
            while (low<high&&a[high]<=temp){
                high--;
            }
            if(low==high){
                break;
            }
            else{
                a[low]=a[high];
            }
            //大于标杆的存在
            while (low<high&&a[low]>=temp){
                low++;
            }
            if(low==high){
                break;
            }
            else{
                a[high] = a[low];
            }
        }
        a[low] = temp;
        return low;
    }
    public int quickSort(int[] a,int low,int high,int K){
        int p = partion(a, low, high);

        if(K==p-low+1){
            return a[p];
        }
        else if(p-low+1>K){
            return quickSort(a, low, p-1, K);
        }
        else
            return quickSort(a, p+1, high, K-(p-low+1));
    }

}
